package demo.letcode.top100;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字n代表生成括号的对数，请你设计一个函数，
 * 对于能够生成所有可能的并且有效的括号组合
 * 输入n=3
 * 输出
 * [((())),(()()),()(()),()()()]
 *
 * 分析
 * 1.组合左括号的数量等于右括号的数量
 * 2.括号组合中任何位置左括号的数量都是大于右括号数量
 *
 * 类比二叉树的前序遍历
 *
 * @author taqo
 * @date 2021/5/8
 */
public class _括号生成 {
    public static void main(String[] args) {
        int n = 3;
        List<String> res = new ArrayList<>();
        def(res, n, n, "");
        System.out.println(res);
    }

    private static void def(List<String> res, int left, int right, String curStr) {
        if (left == 0 && right == 0) {
            res.add(curStr);
            return;
        }
        // 没有左括号
        if (left < 0) {
            return;
        }
        // 如果右括号剩余数小于左括号
        if (right < left) {
            return;
        }

        // 左括号
        def(res, left - 1, right, curStr+"(");
        // 有括号
        def(res, left, right - 1, curStr+")");
    }
}
